#if ((FEATURE_MODE == 2) || (FEATURE_MODE == 0))
#include "sys_tsingma_trie.h"
#include "sys_tsingma_trie_v6.h"
#include "sys_usw_ipuc.h"
#include "ctc_error.h"
#include "sal.h"



#define BITS2WORDS(x)        (((x) + 31)>>5)
#define BITS2SKIPOFF(x)      (((x) + 30)/31)
#define KEY_BIT2IDX(x)       ((32 - (x))>>5)


#define SHL(data, shift, max)   (((shift)>=(max))?0:((data)<<(shift)))
#define SHR(data, shift, max)    (((shift)>=(max))?0:((data)>>(shift)))
#define MASK(len)   (((len)>=32 || (len)==0)?0xFFFFFFFF:((1<<(len))-1))
#define BITMASK(len)  (((len)>=32)?0xFFFFFFFF:((1<<(len))-1))
#define ABS(n) ((((int32)(n)) < 0) ? -(n) : (n))


#define _BITOP(_a, _b, _op)  ((_a) _op (1U << ((_b) &0x1F)))
#define _BITGET(_a, _b) _BITOP(_a, _b, &)
#define _BITSET(_a, _b) _BITOP(_a, _b, |=)
#define _BITCLR(_a, _b) _BITOP(_a, _b, &= ~)


#define BITGETLSBSET(data, msb, lsb)    \
{                                    \
    lsb = 0;                         \
    while ((lsb)<=(msb)) {           \
        if ((data)&(1<<(lsb)))     { \
            break;                   \
        } else { (lsb)++;}           \
    }                                \
    lsb = ((lsb)>(msb))?-1:(lsb);    \
}


#define KEY_APPEND(key, length, skip_addr, skip_len)\
    key[0] = ((key[0]<< (skip_len))|(skip_addr));\
    *length += skip_len;


#define KEY_BITS(bits, key, msb, len)  \
do {                                                  \
        uint32 lsb, data;                              \
        lsb = msb - len;                              \
        data = SHR(key[0], lsb, 32);                  \
        bits = data & (BITMASK((len)));              \
} while (0)


#define LCP_LEN(lcp, key, len1, skip_addr, len2)          \
do {                                                                   \
    uint32 diff;                                                     \
    if ((len1 == 0) || (len2 == 0)) {                                  \
        lcp = 0;                                                       \
    } else {                                                           \
        lcp = len1 < len2 ? len1 : len2;                               \
        diff =  (SHR(key[0], (len1-lcp), 32)) & (BITMASK((lcp)));      \
        diff ^= (SHR(skip_addr, len2 - lcp, 31) & MASK(lcp));\
        while (diff) {                                                 \
            diff >>= 1;                                                \
            --lcp;                                                     \
        }                                                              \
    }                                                                  \
} while (0)


STATIC INLINE int32
_key_shift_right (uint32 *key, uint32 shift)
{
    key[0] = SHR (key[0], shift, 32);
    return CTC_E_NONE;
}


#define TRAVERSE

int32
sys_nalpm_print_trie_node (trie_node_t * trie, void *datum)
{
    if (trie != NULL)
    {
#ifndef CTC_SHELL_DEBUG_ON
        SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP,
             "trie: %p, type %s, skip_addr 0x%x skip_len %d count:%d bpm:0x%x Child[0]:%p Child[1]:%p\n",
             trie, (trie->type == PAYLOAD) ? "P" : "I", trie->skip_addr,
             trie->skip_len, trie->count, trie->bpm, trie->child[0].child_node,
             trie->child[1].child_node);
#endif
    }
    return CTC_E_NONE;
}

STATIC int32
_trie_preorder_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *tmp1, *tmp2;

    if (trie == NULL || !cb)
    {

        return CTC_E_NONE;
    }
    else
    {
        /* make the node delete safe */
        tmp1 = trie->child[0].child_node;
        tmp2 = trie->child[1].child_node;
        rv = cb (trie, user_data);
    }

    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_preorder_traverse (tmp1, cb, user_data);
    }
    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_preorder_traverse (tmp2, cb, user_data);
    }
    return rv;
}

STATIC int32
_trie_postorder_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;

    if (trie == NULL)
    {
        return CTC_E_NONE;
    }

    if (NALPM_E_SUCCESS (rv))
    {
        rv =
            _trie_postorder_traverse (trie->child[0].child_node, cb, user_data);
    }
    if (NALPM_E_SUCCESS (rv))
    {
        rv =
            _trie_postorder_traverse (trie->child[1].child_node, cb, user_data);
    }
    if (NALPM_E_SUCCESS (rv))
    {
        rv = cb (trie, user_data);
    }
    return rv;
}

STATIC int32
_trie_inorder_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *tmp = NULL;

    if (trie == NULL)
    {
        return CTC_E_NONE;
    }

    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_inorder_traverse (trie->child[0].child_node, cb, user_data);
    }

    /* make the trie pointers delete safe */
    tmp = trie->child[1].child_node;

    if (NALPM_E_SUCCESS (rv))
    {
        rv = cb (trie, user_data);
    }

    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_inorder_traverse (tmp, cb, user_data);
    }
    return rv;
}

 STATIC int32
_trie_dump_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *tmp1, *tmp2;
    trie_dump_node_t *p_dump_node = (trie_dump_node_t *)user_data;
    trie_dump_node_t dump_node;

    if (trie == NULL || !cb || !p_dump_node)
    {
        return CTC_E_NONE;
    }
    else
    {
        /* make the node delete safe */
        tmp1 = trie->child[0].child_node;
        tmp2 = trie->child[1].child_node;
        sal_memcpy(&dump_node, p_dump_node, sizeof(trie_dump_node_t));
        rv = cb (trie, &dump_node);
    }

    if ((NULL != tmp1) && NALPM_E_SUCCESS (rv))
    {
        dump_node.father = trie;
        dump_node.father_lvl = p_dump_node->father_lvl + 1;
        rv = _trie_dump_traverse (tmp1, cb, &dump_node);
    }

    if ((NULL != tmp2) && NALPM_E_SUCCESS (rv))
    {
        dump_node.father = trie;
        dump_node.father_lvl = p_dump_node->father_lvl + 1;
        rv = _trie_dump_traverse (tmp2, cb, &dump_node);
    }
    return rv;
}

STATIC int32
_trie_clone_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *tmp1, *tmp2;
    sys_nalpm_clone_para_t* p_para = (sys_nalpm_clone_para_t*)user_data;
    sys_nalpm_clone_para_t para;

    if (trie == NULL || !cb)
    {

        return CTC_E_NONE;
    }
    else
    {
        tmp1 = trie->child[0].child_node;
        tmp2 = trie->child[1].child_node;
        sal_memcpy(&para, p_para, sizeof(sys_nalpm_clone_para_t));
        rv = cb (trie, &para);
    }

    if (NALPM_E_SUCCESS (rv))
    {
        para.bit = 0;
        rv = _trie_clone_traverse (tmp1, cb, &para);
    }
    if (NALPM_E_SUCCESS (rv))
    {
        para.bit = 1;
        rv = _trie_clone_traverse (tmp2, cb, &para);
    }
    return rv;
}

STATIC int32
_trie_clear_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *tmp1, *tmp2;

    if (trie == NULL || !cb)
    {
        return CTC_E_NONE;
    }
    else
    {
        /* make the node delete safe */
        tmp1 = trie->child[0].child_node;
        tmp2 = trie->child[1].child_node;
        rv = cb (trie, NULL);
    }

    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_clear_traverse (tmp1, cb, NULL);
    }
    if (NALPM_E_SUCCESS (rv))
    {
        rv = _trie_clear_traverse (tmp2, cb, NULL);
    }

    return rv;
}
#if 0
STATIC int32
_trie_arrange_fragment_traverse(trie_node_t * trie, trie_callback_f cb, void *user_data)
{
    trie_node_t *tmp1, *tmp2;


    if (trie == NULL || !cb)
    {

        return CTC_E_NONE;
    }
    else
    {
        /* make the node delete safe */
        tmp1 = trie->child[0].child_node;
        tmp2 = trie->child[1].child_node;
        cb (trie, user_data);
    }

    if (1)
    {
        _trie_arrange_fragment_traverse (tmp1, cb, user_data);
    }
    if (1)
    {
        _trie_arrange_fragment_traverse (tmp2, cb, user_data);
    }
    return CTC_E_NONE;
}
#endif

STATIC int32
trie_traverse_propagate_prefix(trie_node_t    *trie,
                               trie_callback_f cb,
                               void  *user_data,
                               uint8 flag)
{
    int32 ret = 0;

    if (trie->type == PAYLOAD && flag == 0)
    {
        ret = cb(trie, user_data);
        if (ret < 0)
        {
            return ret;
        }
    }

    if (trie->child[0].child_node && ret == 0)
    {
        ret = trie_traverse_propagate_prefix(trie->child[0].child_node, cb, user_data, 0);
    }

    if (trie->child[1].child_node && ret == 0)
    {
        ret = trie_traverse_propagate_prefix(trie->child[1].child_node, cb, user_data, 0);
    }

    return ret;
}


int32
sys_nalpm_trie_propagate_prefix(trie_node_t   *trie,
                       uint32             *pfx,
                       uint32              len,
                       trie_callback_f     cb,
                       void               *user_data,
                       uint8 flag)
{
    int32 ret = 0;
    uint32 bit = 0, lcp = 0;

    LCP_LEN (lcp, pfx, len, trie->skip_addr, trie->skip_len);

    if (trie->skip_len == lcp && lcp < len)
    {
        bit = pfx[0] >> ( len - lcp - 1)&0x1;

        if (trie->child[bit].child_node)
        {
            ret = sys_nalpm_trie_propagate_prefix(trie->child[bit].child_node,  pfx, len - lcp - 1, cb, user_data, 0);
        }
    }
    else if (trie->skip_len >= lcp && lcp == len   )
    {
        ret = trie_traverse_propagate_prefix(trie, cb, user_data, flag);
    }

    return ret;
}


STATIC int32
_trie_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data, trie_traverse_order_e_t order)
{
    int32 rv = CTC_E_NONE;

    switch (order)
    {
        case _TRIE_PREORDER_AD_ROUTE_TRAVERSE:
            break;
        case _TRIE_PREORDER_TRAVERSE:
            rv = _trie_preorder_traverse (trie, cb, user_data);
            break;
        case _TRIE_POSTORDER_TRAVERSE:
            rv = _trie_postorder_traverse (trie, cb, user_data);
            break;
        case _TRIE_INORDER_TRAVERSE:
            rv = _trie_inorder_traverse (trie, cb, user_data);
            break;

        case _TRIE_DUMP_TRAVERSE:
            rv = _trie_dump_traverse (trie, cb, user_data);
            break;
        case _TRIE_CLONE_TRAVERSE:
            rv = _trie_clone_traverse (trie, cb, user_data);
            break;
        case _TRIE_CLEAR_TRAVERSE:
            rv = _trie_clear_traverse (trie, cb, user_data);
            break;

        default:
            break;
    }

    return rv;
}

int32
sys_nalpm_trie_traverse (trie_node_t * trie, trie_callback_f cb,
        void *user_data, trie_traverse_order_e_t order)
{
    if (trie == NULL)
    {
        return CTC_E_NONE;
    }
    else
    {
        return _trie_traverse (trie, cb, user_data, order);
    }
}

STATIC int32
_trie_dump (trie_node_t * trie, trie_callback_f cb,
        void *user_data, uint32 level)
{
    if (trie == NULL)
    {
        if (cb)
        {
            cb (trie, user_data);
        }
        return CTC_E_NONE;
    }
    else
    {
        if (cb)
        {
            cb (trie, user_data);
        }
        else
        {
            uint32 lvl = level;
            while (lvl)
            {
#ifndef CTC_SHELL_DEBUG_ON                
                if (lvl == 1)
                {
                    SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, "|-");
                }
                else
                {
                    SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, "| ");
                }
#endif
                lvl--;
            }
            sys_nalpm_print_trie_node (trie, NULL);
        }
    }

    _trie_dump (trie->child[0].child_node, cb, user_data, level + 1);
    _trie_dump (trie->child[1].child_node, cb, user_data, level + 1);
    return CTC_E_NONE;
}

int32
sys_nalpm_trie_dump (trie_t * trie, trie_callback_f cb, void *user_data)
{
    if (trie->trie)
    {
        return _trie_dump (trie->trie, cb, user_data, 0);
    }
    else
    {
        return CTC_E_INVALID_PARAM;
    }
}

STATIC int32
_trie_find_lpm (trie_node_t *parent,
        trie_node_t * trie,
        uint32 *key,
        uint32 length,
        trie_node_t ** payload, trie_callback_f cb, void *user_data, uint32 last_total_skip_len)
{
    uint32 lcp = 0;
    int32 bit = 0, rv = CTC_E_NONE;

    if (!trie)
    {
        return CTC_E_INVALID_PARAM;
    }

    if (parent == trie)
    {
        /* root node */
        trie->total_skip_len = trie->skip_len;
    }
    else
    {
        /* not root node need add its parent's total skip length + slash + itself's skip length*/
        trie->total_skip_len = (last_total_skip_len + trie->skip_len + 1);
    }

    LCP_LEN (lcp, key, length, trie->skip_addr, trie->skip_len);

    if ((length > trie->skip_len) && (lcp == trie->skip_len))
    {
        if (trie->type == PAYLOAD)
        {
            /* lpm cases */
            if (payload != NULL  && 1 != trie->dirty_flag)
            {
                /* update lpm result */
                *payload = trie;
                parent = trie;
            }
            else if(payload != NULL  && 1 == trie->dirty_flag)
            {
                *payload = parent;
            }

            if (cb != NULL)
            {
                /* callback with any nodes which is shorter and matches the prefix */
                rv = cb (trie, user_data);
                if (NALPM_E_FAILURE (rv))
                {
                    /* early bailout if there is error in callback handling */
                    return rv;
                }
            }
        }

        bit = (key[KEY_BIT2IDX (length - lcp)] &  SHL (1, (length - lcp - 1) &0x1F,  32)) ? 1 : 0;

        /* based on next bit branch left or right */
        if (trie->child[bit].child_node)
        {
            return _trie_find_lpm (parent, trie->child[bit].child_node, key,
                    length - lcp - 1, payload, cb, user_data, trie->total_skip_len);
        }
    }
    else if ((length == trie->skip_len) && (lcp == length))
    {
        if (trie->type == PAYLOAD)
        {
            /* exact match case */
            if (payload != NULL)
            {
                /* lpm is exact match */
                *payload = (1 == trie->dirty_flag)?parent:trie;
            }

            if (cb != NULL)
            {
                /* callback with the exact match node */
                rv = cb (trie, user_data);
                if (NALPM_E_FAILURE (rv))
                {
                    /* early bailout if there is error in callback handling */
                    return rv;
                }
            }
        }
    }
    return rv;
}

int32
sys_nalpm_trie_find_lpm (trie_t * trie,
        uint32 *key, uint32 length, trie_node_t ** payload, uint8 is_route)
{
    *payload = NULL;

    if(is_route)
    {
        SYS_NALPM_CONVERT_TO_LSB(key, length, trie->v6_key);
    }

    if (trie->trie)
    {
        if (trie->v6_key)
        {
            return sys_trie_v6_find_lpm (trie->trie, trie->trie, key, length, payload, NULL, NULL, 0);
        }
        else
        {
            return _trie_find_lpm (trie->trie, trie->trie, key, length, payload, NULL, NULL, 0);
        }
    }

    return CTC_E_NOT_EXIST;
}


STATIC int32
_trie_skip_node_alloc (trie_node_t ** node, uint32 *key,
        uint32 *bpm, uint32 msb,
        uint32 skip_len, trie_node_t * payload, uint32 count)
{
    int32 lsb = 0, msbpos = 0, lsbpos = 0, bit = 0, index;
    trie_node_t *child = NULL, *skip_node = NULL;

    /* calculate lsb bit position, also 1 based */

    lsb = ((msb) ? msb + 1 - skip_len : msb);
    if (msb)
    {
        for (index = BITS2SKIPOFF (lsb), lsbpos = lsb - 1; index <= BITS2SKIPOFF (msb); index++)
        {
            /* each loop process _MAX_SKIP_LEN number of bits?? */
            if (lsbpos == lsb - 1)
            {
                /* (lsbpos == lsb-1) is only true for first node (loop) here */
                skip_node = payload;
            }
            else
            {
                /* other nodes need to be created */
                skip_node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);
                if (NULL == skip_node)
                {
                    return CTC_E_NO_MEMORY;
                }
            }

            /* init memory */
            sal_memset (skip_node, 0, sizeof (trie_node_t));

            /* calculate msb bit position of current chunk of bits we are processing */
            msbpos = index * 31 - 1; /*msbpos = 30*/

            if (msbpos > msb - 1)
            {
                msbpos = msb - 1;
            }

            /* calculate the skip_len of the created node */
            if (msbpos - lsbpos < 31)
            {
                skip_node->skip_len = msbpos - lsbpos + 1;
            }
            else
            {
                skip_node->skip_len = 31;
            }

            /* calculate the skip_addr (skip_length number of bits).
             * skip might be skipping bits on 2 different words
             * if msb & lsb spawns 2 word boundary in worst case
             */
            if (BITS2WORDS (msbpos + 1) != BITS2WORDS (lsbpos + 1))
            {
                /* pull snippets from the different words & fuse */
                skip_node->skip_addr = key[KEY_BIT2IDX (msbpos + 1)] & MASK ((msbpos + 1)&0x1F);
                skip_node->skip_addr = SHL (skip_node->skip_addr, skip_node->skip_len - ((msbpos + 1) &0x1F), 32);
                skip_node->skip_addr |= SHR (key[KEY_BIT2IDX (lsbpos + 1)], (lsbpos &0x1F), 32);
            }
            else
            {
                skip_node->skip_addr =  SHR (key[KEY_BIT2IDX (msbpos + 1)], (lsbpos &0x1F), 32);
            }

            /* set up the chain of child pointer, first node has no child since "child" was inited to NULL */
            if (child)
            {
                skip_node->child[bit].child_node = child;
            }

            /* calculate child pointer for next loop. NOTE: skip_addr has not been masked
             * so we still have the child bit in the skip_addr here.
             */
            bit = (skip_node->skip_addr & SHL (1, skip_node->skip_len - 1, 31)) ? 1 : 0;

            /* calculate node type */
            if (lsbpos == lsb - 1)
            {
                /* first node is payload */
                skip_node->type = PAYLOAD;
            }
            else
            {
                /* other nodes are internal nodes */
                skip_node->type = INTERNAL;
            }

            /* all internal nodes will have the same "count" as the payload node */
            skip_node->count = count;

            /* advance lsb to next word */
            lsbpos += skip_node->skip_len;


            /* for all child nodes 0/1 is implicitly obsorbed on parent */
            if (msbpos != msb - 1)
            {
                /* msbpos == (msb-1) is only true for the first node */
                skip_node->skip_len--;
            }


            skip_node->skip_addr &= MASK (skip_node->skip_len);
            child = skip_node;
        }
    }
    else
    {
        /* skip_len == 0 case, create a payload node with skip_len = 0 and bpm should be 1 bits only
         * bit 0 and bit "skip_len" are same bit (bit 0).
         */
        skip_node = payload;
        sal_memset (skip_node, 0, sizeof (trie_node_t));
        skip_node->type = PAYLOAD;
        skip_node->count = count;
    }

    *node = skip_node;
    return CTC_E_NONE;
}

STATIC int32
_trie_insert (trie_node_t * trie, uint32 *key,
        uint32 *bpm, uint32 length, trie_node_t * payload,/* payload node */
        trie_node_t ** child /* child pointer if the child is modified */ )
{
    uint32 lcp;
    int32 rv = CTC_E_NONE, bit = 0;
    trie_node_t *node = NULL;

    *child = NULL;


    LCP_LEN (lcp, key, length, trie->skip_addr, trie->skip_len);

    /* insert cases:
     * 1 - new key could be the parent of existing node
     * 2 - new node could become the child of a existing node
     * 3 - internal node could be inserted and the key becomes one of child
     * 4 - internal node is converted to a payload node */

    /* if the new key qualifies as new root do the inserts here */
    if (lcp == length)   /* insert shorter prefix*/
    {       /* guaranteed: length < 31 */
        if (trie->skip_len == lcp)
        {
            if (trie->type != INTERNAL)
            {
                /* duplicate */
                return CTC_E_EXIST;
            }
            else
            {
                /* change the internal node to payload node */
                _CLONE_TRIE_NODE_ (payload, trie);
                mem_free (trie);
                payload->type = PAYLOAD;
                payload->count++;
                *child = payload;

                return CTC_E_NONE;
            }
        }
        else
        {/* skip length can never be less than lcp implcitly here */
            /* this node is new parent for the old trie node */
            /* lcp is the new skip length */
            _CLONE_TRIE_NODE_ (payload, trie);
            *child = payload;

            bit = (trie->skip_addr & SHL (1, trie->skip_len - length - 1,  31)) ? 1 : 0;
            trie->skip_addr &= MASK (trie->skip_len - length - 1);
            trie->skip_len -= (length + 1);

            payload->dirty_flag = 0;
            payload->skip_addr = (length > 0) ? key[KEY_BIT2IDX (length)] : 0;
            payload->skip_addr &= MASK (length);
            payload->skip_len = length;
            payload->child[bit].child_node = trie;
            payload->child[!bit].child_node = NULL;
            payload->type = PAYLOAD;
            payload->count++;

        }
    }
    else if (lcp == trie->skip_len)  /* insert longer prefix*/
    {
        /* key length is implictly greater than lcp here */
        /* decide based on key's next applicable bit */
        bit = (key[KEY_BIT2IDX (length - lcp)] & SHL (1, (length - lcp - 1) &0x1F, 32)) ? 1 : 0;

        if (!trie->child[bit].child_node)
        {
            /* the key is going to be one of the child of existing node */
            /* should be the child */
            rv = _trie_skip_node_alloc (&node, key, bpm, length - lcp - 1, length - lcp - 1, payload, 1);
            if (NALPM_E_SUCCESS (rv))
            {
                trie->child[bit].child_node = node;
                trie->count++;
            }
            else
            {
#ifndef CTC_SHELL_DEBUG_ON
                SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, "\n Error on trie skip node allocaiton [%d]!!!!\n", rv);
#endif
            }
        }
        else
        {
            rv = _trie_insert (trie->child[bit].child_node, key, bpm, length - lcp - 1, payload, child);
            if (NALPM_E_SUCCESS (rv))
            {
                trie->count++;
                if (*child != NULL)
                {/* chande the old child pointer to new child */
                    trie->child[bit].child_node = *child;
                    *child = NULL;
                }
            }
        }
    }
    else
    {
        trie_node_t *newchild = NULL;

        /* need to introduce internal nodes */
        node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);
        if(node == NULL)
        {
            return CTC_E_NO_MEMORY;
        }
        sal_memset(node, 0, sizeof (trie_node_t));
        _CLONE_TRIE_NODE_ (node, trie);
        /* clone from trie node but dirty_flag should initialize as 0 */
        node->dirty_flag = 0;

        rv = _trie_skip_node_alloc (&newchild, key, bpm, ((lcp) ? length - lcp - 1 : length - 1),  length - lcp - 1, payload, 1);

        if (NALPM_E_SUCCESS (rv))
        {

            bit = (key[KEY_BIT2IDX (length - lcp)] & SHL (1, (length - lcp - 1) &0x1F, 32)) ? 1 : 0;
            node->child[!bit].child_node = trie;
            node->child[bit].child_node = newchild;
            node->type = INTERNAL;
            node->skip_addr =  SHR (trie->skip_addr, trie->skip_len - lcp, 31);
            node->skip_len = lcp;
            node->count++;

            *child = node;
            trie->skip_addr &= MASK (trie->skip_len - lcp - 1);
            trie->skip_len -= (lcp + 1);
        }
        else
        {
#ifndef CTC_SHELL_DEBUG_ON
            SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, "\n Error on trie skip node allocaiton [%d]!!!!\n",
                    rv);
#endif                    
            mem_free (node);
        }
    }

    return rv;
}

/*
 * Function:
 *     sys_nalpm_trie_insert
 * Purpose:
 *     Inserts provided prefix/length in to the trie
 */
int32
sys_nalpm_trie_insert (trie_t * trie, uint32 *key, uint32 *bpm, uint32 length, trie_node_t * payload, uint8 is_route)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *child = NULL;

    if (!trie)
        return CTC_E_INVALID_PARAM;

    if(is_route)
    {
        SYS_NALPM_CONVERT_TO_LSB(key, length, trie->v6_key);
    }

    if (trie->trie == NULL)
    {
        if (trie->v6_key)
        {
            rv = sys_trie_v6_skip_node_alloc (&trie->trie, key, bpm, length, length, payload, 1);
        }
        else
        {
            rv = _trie_skip_node_alloc (&trie->trie, key, bpm, length, length, payload, 1);
        }
    }
    else
    {
        if (trie->v6_key)
        {
            rv =
                sys_trie_v6_insert (trie->trie, key, bpm, length, payload, &child);
        }
        else
        {
            rv = _trie_insert (trie->trie, key, bpm, length, payload, &child);
        }
        if (child)
        {           /* chande the old child pointer to new child */
            trie->trie = child;
        }
    }

    return rv;
}

int32
sys_nalpm_trie_fuse_child (trie_node_t * trie, int32 bit)
{
    trie_node_t *child = NULL;
    int32 rv = CTC_E_NONE;


    bit = (bit > 0) ? 1 : 0;
    child = trie->child[bit].child_node;

    if (child == NULL)
    {
        return CTC_E_INVALID_PARAM;
    }
    else
    {
        if (trie->skip_len + child->skip_len + 1 <= 31)
        {

            if (trie->skip_len == 0)
                trie->skip_addr = 0;

            if (child->skip_len < 31)
            {
                trie->skip_addr =  SHL (trie->skip_addr, child->skip_len + 1, 31);
            }

            trie->skip_addr |= SHL (bit, child->skip_len, 31);
            child->skip_addr |= trie->skip_addr;
            child->skip_len += trie->skip_len + 1;
            /* do not free payload nodes as they are user managed */
            if (trie->type == INTERNAL)
            {
                mem_free (trie);
            }

        }
    }

    return rv;
}

STATIC int32
_trie_delete (trie_node_t * trie,
        uint32 *key,
        uint32 length,
        trie_node_t ** payload, trie_node_t ** child)
{
    uint32 lcp;
    int32 rv = CTC_E_NONE, bit = 0;
    trie_node_t *node = NULL;

    *child = NULL;

    /* check a section of key, return the number of matched bits and value of next bit */
    LCP_LEN (lcp, key, length, trie->skip_addr, trie->skip_len);

    if (length > trie->skip_len)
    {

        if (lcp == trie->skip_len)
        {

            bit = (key[KEY_BIT2IDX (length - lcp)] & SHL (1, (length - lcp - 1) &0x1F, 32)) ? 1 : 0;

            /* based on next bit branch left or right */
            if (trie->child[bit].child_node)
            {
                /* has child node, keep searching */
                rv = _trie_delete (trie->child[bit].child_node, key, length - lcp - 1, payload, child);

                if (rv == CTC_E_IN_USE)
                {

                    trie->child[bit].child_node = NULL;	/* mem_free the child */
                    rv = CTC_E_NONE;
                    trie->count--;

                    if (trie->type == INTERNAL)
                    {
                        bit = (bit == 0) ? 1 : 0;

                        if (trie->child[bit].child_node == NULL)
                        {
                            /* parent and child connected, mem_free the middle-node itself */
                            mem_free (trie);
                            rv = CTC_E_IN_USE;
                        }
                        else
                        {
                            /* fuse the parent & child */
                            if (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= 31)
                            {
                                *child = trie->child[bit].child_node;
                                rv = sys_nalpm_trie_fuse_child (trie, bit);
                                if (rv != CTC_E_NONE)
                                {
                                    *child = NULL;
                                }
                            }
                        }
                    }
                }
                else if (NALPM_E_SUCCESS (rv))
                {
                    trie->count--;
                    /* update child pointer if applicable */
                    if (*child != NULL)
                    {
                        trie->child[bit].child_node = *child;
                        *child = NULL;
                    }
                }
            }
            else
            {
                /* no child node case 0: not found */
                rv = CTC_E_NOT_EXIST;
            }

        }
        else
        {
            /* some bits are not matching, case 0: not found */
            rv = CTC_E_NOT_EXIST;
        }
    }
    else if (length == trie->skip_len)
    {
        /* when length equal to skip_len, unless this is a payload node
         * and it's an exact match (lcp == length), we can not found a match
         */
        if (!((lcp == length) && (trie->type == PAYLOAD)))
        {
            rv = CTC_E_NOT_EXIST;
        }
        else
        {
            /* payload node can be deleted */
            /* if this node has 2 children update it to internal node */
            rv = CTC_E_NONE;

            if (trie->child[0].child_node && trie->child[1].child_node)
            {
                /* the node has 2 children, update it to internal node */
                node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);
                if (node == NULL)
                {
                    return CTC_E_NO_MEMORY;
                }
                _CLONE_TRIE_NODE_ (node, trie);
                node->type = INTERNAL;
                node->count--;
                *child = node;
            }
            else if (trie->child[0].child_node || trie->child[1].child_node)
            {
                /* if this node has 1 children fuse the children with this node */
                bit = (trie->child[0].child_node) ? 0 : 1;
                trie->count--;
                if (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= 31)
                {
                    /* able to fuse the node with its child node */
                    *child = trie->child[bit].child_node;
                    rv = sys_nalpm_trie_fuse_child (trie, bit);
                    if (rv != CTC_E_NONE)
                    {
                        *child = NULL;
                    }
                }
                else
                {
                    /* convert it to internal node, we need to alloc new memory for internal nodes
                     * since the old payload node memory will be freed by caller
                     */
                    node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);
                    if(node == NULL)
                    {
                        return CTC_E_NO_MEMORY;
                    }
                    _CLONE_TRIE_NODE_ (node, trie);
                    node->type = INTERNAL;
                    *child = node;
                }
            }
            else
            {
                rv = CTC_E_IN_USE;
            }

            *payload = trie;
        }
    }
    else
    {
        /* key length is shorter, no match if it's internal node,
         * will not exact match even if this is a payload node
         */
        rv = CTC_E_NOT_EXIST;	/* case 0: not found */
    }

    return rv;
}

/*
 * Function:
 *     sys_nalpm_trie_delete
 * Purpose:
 *     Deletes provided prefix/length in to the trie
 */
    int32
sys_nalpm_trie_delete (trie_t * trie,
        uint32 *key, uint32 length, trie_node_t ** payload, uint8 is_route)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *child = NULL;

    if(is_route)
    {
        SYS_NALPM_CONVERT_TO_LSB(key, length, trie->v6_key);
    }

    if (trie->trie)
    {
        if (trie->v6_key)
        {
            rv = sys_trie_v6_delete (trie->trie, key, length, payload, &child);
        }
        else
        {
            rv = _trie_delete (trie->trie, key, length, payload, &child);
        }
        if (rv == CTC_E_IN_USE)
        {
            /* the head node of trie was deleted, reset trie pointer to null */
            trie->trie = NULL;
            rv = CTC_E_NONE;
        }
        else if (rv == CTC_E_NONE && child != NULL)
        {
            trie->trie = child;
        }
    }
    else
    {
        rv = CTC_E_NOT_EXIST;
    }
    return rv;
}

STATIC int32
_trie_split (trie_node_t * trie,
        uint32 *pivot,
        uint32 *length,
        uint32 *split_count,
        trie_node_t ** split_node,
        trie_node_t ** child,
        const uint32 max_count,
        const uint32 max_split_len,
        const int32 split_to_pair,
        uint32 *bpm, trie_split_states_e_t * state, const int32 max_split_count)
{
    int32 bit = 0, rv = CTC_E_NONE;


    if (trie->child[0].child_node && trie->child[1].child_node)
    {
        bit = (trie->child[0].child_node->count >  trie->child[1].child_node->count) ? 0 : 1;
    }
    else
    {
        bit = (trie->child[0].child_node) ? 0 : 1;
    }

    /* start building the pivot */
    KEY_APPEND (pivot, length, trie->skip_addr, trie->skip_len);

    if (trie->count <= max_split_count && (((*length == max_split_len) && (trie->count != max_count)) || (!trie->child[bit].child_node) ||
        (ABS (trie->child[bit].child_node->count * 2 - max_count * 1) >
    ABS (trie->count * 2 - max_count * 1))))
    {
        *split_node = trie;
        *split_count = trie->count;

        *state = TRIE_SPLIT_STATE_PRUNE_NODES;
        return rv;
    }
    else
    {
        KEY_APPEND (pivot, length, bit, 1);

        rv = _trie_split (trie->child[bit].child_node,
                pivot, length,
                split_count, split_node,
                child, max_count, max_split_len,
                split_to_pair, bpm, state, max_split_count);
    }


    /* free up internal nodes if applicable */
    switch (*state)
    {
        case TRIE_SPLIT_STATE_PRUNE_NODES:
            if (trie->count == *split_count)
            {
                mem_free (trie);
            }
            else
            {
                /* fuse with child if possible */
                trie->child[bit].child_node = NULL;
                bit = (bit == 0) ? 1 : 0;
                trie->count -= *split_count;

                /* optimize more */
                if ((trie->type == INTERNAL) &&
                        (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= 31))
                {
                    *child = trie->child[bit].child_node;
                    rv = sys_nalpm_trie_fuse_child (trie, bit);
                    if (rv != CTC_E_NONE)
                    {
                        *child = NULL;
                    }
                }
                *state = TRIE_SPLIT_STATE_DONE;
            }
            break;

        case TRIE_SPLIT_STATE_DONE:
            if (*child != NULL)
            {
                trie->child[bit].child_node = *child;
                *child = NULL;
            }
            trie->count -= *split_count;
            break;

        default:
            break;
    }

    return rv;
}


int32
sys_nalpm_trie_split (trie_t * trie,
        const uint32 max_split_len,
        const int32 split_to_pair,
        uint32 *pivot,
        uint32 *length,
        trie_node_t ** split_trie_root,
        uint32 *bpm,
        uint8 payload_node_split,
        const int32 max_split_count)
{
    int32 rv = CTC_E_NONE;
    uint32 split_count = 0, max_count = 0;
    trie_node_t *child = NULL, *node = NULL, clone;
    trie_split_states_e_t state = TRIE_SPLIT_STATE_NONE;
#ifndef CTC_SHELL_DEBUG_ON
    trie_node_t *root;

    root = trie->trie;
#endif
    *length = 0;

    if (trie->trie)
    {
#ifndef CTC_SHELL_DEBUG_ON
        uint32 t_cnt, l_cnt, r_cnt;
        t_cnt = trie->trie->count;
        l_cnt = (trie->trie->child[0].child_node != NULL) ? trie->trie->child[0].child_node->count : 0;
        r_cnt = (trie->trie->child[1].child_node != NULL) ? trie->trie->child[1].child_node->count : 0;
#endif
        if (payload_node_split)
            state = TRIE_SPLIT_STATE_PAYLOAD_SPLIT;

        max_count = trie->trie->count;

        if (trie->v6_key)
        {
            sal_memset (pivot, 0, 16);
            rv =sys_trie_v6_split (trie->trie, pivot, length, &split_count, split_trie_root, &child, max_count, max_split_len, split_to_pair, bpm, &state, max_split_count);
        }
        else
        {
            sal_memset (pivot, 0, 8);
            rv = _trie_split (trie->trie, pivot, length, &split_count, split_trie_root, &child, max_count, max_split_len, split_to_pair, bpm, &state, max_split_count);
        }

        if (NALPM_E_SUCCESS (rv) && (TRIE_SPLIT_STATE_DONE == state))
        {
            if (trie->trie == NULL)
            {
                trie_t *c1, *c2;
                sys_nalpm_trie_init (32, &c1);
                sys_nalpm_trie_init (32, &c2);

                c1->trie = child;
                c2->trie = *split_trie_root;
#ifndef CTC_SHELL_DEBUG_ON
                SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, "error:dumping the 2 child trees\n");
#endif
                sys_nalpm_trie_dump (c1, 0, 0);
                sys_nalpm_trie_dump (c2, 0, 0);
            }

            /* update the child pointer if child was pruned */
            if (child != NULL)
            {
                trie->trie = child;
            }

            sal_memcpy (&clone, *split_trie_root, sizeof (trie_node_t));
            child = *split_trie_root;


            if (trie->v6_key)
            {
                rv = sys_trie_v6_skip_node_alloc (&node, pivot, NULL, *length, *length, child, child->count);
            }
            else
            {
                rv = _trie_skip_node_alloc (&node, pivot, NULL,  *length, *length, child, child->count);
            }

            if (NALPM_E_SUCCESS (rv))
            {
                if (clone.type == INTERNAL)
                {
                    child->type = INTERNAL;	/* since skip alloc would have reset it to payload */
                }
                child->child[0].child_node = clone.child[0].child_node;
                child->child[1].child_node = clone.child[1].child_node;
                *split_trie_root = node;
            }
        }
        else
        {
            if (NALPM_E_SUCCESS (rv) && (TRIE_SPLIT_STATE_PRUNE_NODES == state))
            {
#ifndef CTC_SHELL_DEBUG_ON
                SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_INFO, "retry[%d/%d/%d] fail[%p]\r\n", t_cnt, l_cnt, r_cnt, root);
#endif
                rv = CTC_E_NOT_READY;
            }
            else
            {
#ifndef CTC_SHELL_DEBUG_ON
                SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_INFO, "!split[%d/%d/%d] fail[%p]\r\n", t_cnt, l_cnt, r_cnt, root);
#endif
            }
        }
    }
    else
    {
        rv = CTC_E_INVALID_PARAM;
    }

    return rv;
}

int32
_sys_nalpm_clone_node(trie_node_t* node, void* data)
{
    sys_nalpm_clone_para_t* clone_para = (sys_nalpm_clone_para_t*)data;
    trie_node_t* new_node = NULL;

    if(node->type == INTERNAL)
    {
        new_node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);
        if (NULL == new_node)
        {
            return CTC_E_NO_MEMORY;
        }
        sal_memcpy(new_node, node, sizeof(trie_node_t));
    }
    else
    {
        new_node = mem_malloc(MEM_IPUC_MODULE, (sizeof(trie_node_t) + sizeof(trie_node_t*)));
        if (NULL == new_node)
        {
            return CTC_E_NO_MEMORY;
        }
        sal_memcpy(new_node, node, (sizeof(trie_node_t) + sizeof(trie_node_t*)));
    }
    new_node->child[0].child_node = NULL;
    new_node->child[1].child_node = NULL;
    clone_para->father->child[clone_para->bit].child_node= new_node;
    clone_para->father = new_node;

    return CTC_E_NONE;
}

int32
sys_nalpm_trie_clone(trie_t* trie, trie_t** clone_trie)
{
    sys_nalpm_clone_para_t para;
    trie_node_t* root_node = NULL;
    int32 rv = CTC_E_NONE;
    sal_memset (&para, 0, sizeof (sys_nalpm_clone_para_t));

    if (!trie->trie)
    {
        return CTC_E_NONE;
    }

    *clone_trie = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_t), trie_t);
    if(*clone_trie == NULL)
    {
        return CTC_E_NO_MEMORY;
    }

    sal_memcpy (*clone_trie, trie, sizeof (trie_t));

    if(trie->trie->type == INTERNAL)
    {
        root_node = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_node_t), trie_node_t);

        if(root_node == NULL)
        {
            mem_free(*clone_trie);
            return CTC_E_NO_MEMORY;
        }
        sal_memcpy(root_node, trie->trie, sizeof(trie_node_t));
        root_node->child[0].child_node = NULL;
        root_node->child[1].child_node = NULL;
    }
    else
    {
        root_node = mem_malloc(MEM_IPUC_MODULE, (sizeof(trie_node_t) + sizeof(trie_node_t*)));

        if(root_node == NULL)
        {
            mem_free(*clone_trie);
            return CTC_E_NO_MEMORY;
        }
        sal_memcpy(root_node, trie->trie, (sizeof(trie_node_t) + sizeof(trie_node_t*)));
        root_node->child[0].child_node = NULL;
        root_node->child[1].child_node = NULL;
    }
    (*clone_trie)->trie = root_node;

    para.father = root_node;
    para.bit = 0;
    rv = sys_nalpm_trie_traverse (trie->trie->child[0].child_node, _sys_nalpm_clone_node,(void *)&para, _TRIE_CLONE_TRAVERSE);
    if (NALPM_E_FAILURE(rv))
    {
        goto error0;
    }
    para.father = root_node;
    para.bit = 1;
    rv = sys_nalpm_trie_traverse (trie->trie->child[1].child_node, _sys_nalpm_clone_node,(void *)&para, _TRIE_CLONE_TRAVERSE);
    if (NALPM_E_FAILURE(rv))
    {
        goto error0;
    }

    return CTC_E_NONE;

error0:
    sys_nalpm_trie_clear((*clone_trie)->trie);
    sys_nalpm_trie_destroy(*clone_trie);

    return rv;
}

int32
_sys_nalpm_clear_node(trie_node_t* node, void* data)
{
    if(node != NULL)
    {
        mem_free(node);
        node = NULL;
    }
    return CTC_E_NONE;
}

int32
sys_nalpm_trie_clear(trie_node_t* node)
{
    int32 rv = CTC_E_NONE;

    rv = sys_nalpm_trie_traverse (node, _sys_nalpm_clear_node, NULL, _TRIE_CLEAR_TRAVERSE);

    return rv;
}

/*
 * Function:
 *     sys_nalpm_trie_init
 * Purpose:
 *     allocates a trie & initializes it
 */
    int32
sys_nalpm_trie_init (uint32 max_key_len, trie_t ** ptrie)
{
    trie_t *trie = mem_malloc2(MEM_IPUC_MODULE, sizeof (trie_t), trie_t);
    if(trie == NULL)
    {
        return CTC_E_NO_MEMORY;
    }
    sal_memset (trie, 0, sizeof (trie_t));

    if (max_key_len == 32)
    {
        trie->v6_key = FALSE;
    }
    else if (max_key_len == 128)
    {
        trie->v6_key = TRUE;
    }
    else
    {
        mem_free (trie);
        return CTC_E_INVALID_PARAM;
    }

    trie->trie = NULL;/* means nothing is on teie */
    *ptrie = trie;
    return CTC_E_NONE;
}

int32
sys_nalpm_trie_destroy (trie_t * trie)
{
    mem_free (trie);
    trie = NULL;
    return CTC_E_NONE;
}

STATIC int32
_trie_skip_node_free(trie_node_t *trie,
                                uint32 *key,
                                uint32 length)
{
    uint32 lcp = 0;
    int32 bit = 0, rv = CTC_E_NONE;

    LCP_LEN(lcp, key, length, trie->skip_addr, trie->skip_len);

    if (length > trie->skip_len)
    {
        if (lcp == trie->skip_len)
        {
            bit = (key[KEY_BIT2IDX(length - lcp)] &  (1 << ((length - lcp - 1) &0x1F))) ? 1:0;

            /* There should be only one branch on the chain until the end node */
            if (!trie->child[0].child_node == !trie->child[1].child_node)
            {
                return CTC_E_INVALID_PARAM;
            }

            /* based on next bit branch left or right */
            if (trie->child[bit].child_node)
            {
                rv = _trie_skip_node_free(trie->child[bit].child_node, key, length - lcp - 1);
                if (NALPM_E_SUCCESS(rv))
                {
                    mem_free(trie);
                }

                return rv;
            }
            else
            {
                return CTC_E_NOT_EXIST; /* not found */
            }
        }
        else
        {
            return CTC_E_NOT_EXIST; /* not found */
        }
    }
    else if (length == trie->skip_len)
    {
        if (lcp == length)
        {
            return CTC_E_NONE;
        }
        else
        {
            return CTC_E_NOT_EXIST;
        }
    }
    else
    {
        return CTC_E_NOT_EXIST; /* not found */
    }

    return 0;
}
#if 0
STATIC  int32
_print_trie_node (trie_node_t * trie, void *datum)
{
    if (trie != NULL)
    {

        sal_printf("trie: %p, type %s, skip_addr 0x%x skip_len %d count:%d bpm:0x%x Child[0]:%p Child[1]:%p\n",
             trie, (trie->type == PAYLOAD) ? "P" : "I", trie->skip_addr,
             trie->skip_len, trie->count, trie->bpm, trie->child[0].child_node,
             trie->child[1].child_node);
    }
    return CTC_E_NONE;
}
#endif
STATIC int32
_trie_search(trie_node_t *trie,
            uint32 *key,
            uint32 length,
            trie_node_t **payload,
            uint32 *result_key,
            uint32 *result_len,
            uint32 dump,
            uint32 find_pivot)
{
    uint32 lcp = 0;
    int32 bit = 0;

    LCP_LEN(lcp,key, length, trie->skip_addr, trie->skip_len);
#if 0
    if (dump)
    {
        _print_trie_node(trie, (uint32 *)1);
    }
#endif
    if (length > trie->skip_len)
    {
        if (lcp == trie->skip_len)
        {
            bit = (key[KEY_BIT2IDX(length - lcp)] & (1 << ((length - lcp - 1) % 32))) ? 1:0;
            if (dump)
            {
                sal_printf(" Length: %d Next-Bit[%d] \n", length, bit);
            }

            if (result_key)
            {
                KEY_APPEND(result_key, result_len, trie->skip_addr, trie->skip_len);
            }

            /* based on next bit branch left or right */
            if (trie->child[bit].child_node)
            {
                if (result_key)
                {
                    KEY_APPEND(result_key, result_len, bit, 1);

                }

                return _trie_search(trie->child[bit].child_node, key,
                                    length - lcp - 1, payload,
                                    result_key, result_len, dump, find_pivot);
            }

        }
    }
    else if (length == trie->skip_len)
    {
        if (lcp == length)
        {
            if (dump)
            {
#ifndef CTC_SHELL_DEBUG_ON
                SYS_IPUC_DBG_OUT(CTC_DEBUG_LEVEL_DUMP, ": MATCH \n");
#endif
            }
            *payload = trie;
            if (trie->type != PAYLOAD && !find_pivot)
            {
                return CTC_E_NOT_EXIST;
            }

            if (result_key)
            {
                KEY_APPEND(result_key, result_len, trie->skip_addr, trie->skip_len);

            }

            return CTC_E_NONE;
        }

    }
    else
    {
        if (lcp == length && find_pivot)
        {
            *payload = trie;
            if (result_key)
            {
                KEY_APPEND(result_key, result_len, trie->skip_addr, trie->skip_len);

            }

            return CTC_E_NONE;
        }


    }

    return CTC_E_NOT_EXIST;
}


STATIC int32
_trie_insert2(trie_node_t *trie,
              uint32 *key,
              uint32 *bpm,
              uint32 length,
              trie_node_t *payload, /* payload node */
              trie_node_t **child, /* child pointer if the child is modified */
              int32 child_count)
{
    uint32 lcp;
    int32 rv = CTC_E_NONE, bit = 0;
    trie_node_t *node = NULL;

    *child = NULL;

    LCP_LEN(lcp, key, length, trie->skip_addr, trie->skip_len);

    /* if the new key qualifies as new root do the inserts here */
    if (lcp == length)
    {
        if (trie->skip_len == lcp)
        {
            if (trie->type != INTERNAL)
            {
                return CTC_E_EXIST;
            }
            else
            {
                /* change the internal node to payload node */
                _CLONE_TRIE_NODE_(payload, trie);
                mem_free(trie);
                payload->type = PAYLOAD;
                payload->count += child_count;
                *child = payload;

                return CTC_E_NONE;
            }
        }
        else
        {
            /* this node is new parent for the old trie node */
            /* lcp is the new skip length */
            _CLONE_TRIE_NODE_(payload, trie);
            *child = payload;

            bit = (trie->skip_addr & SHL(1, trie->skip_len - length - 1, 31)) ? 1 : 0;
            trie->skip_addr &= MASK(trie->skip_len - length - 1);
            trie->skip_len  -= (length + 1);

            payload->skip_addr = (length > 0) ? key[KEY_BIT2IDX(length)] : 0;
            payload->skip_addr &= MASK(length);
            payload->skip_len  = length;
            payload->child[bit].child_node = trie;
            payload->child[!bit].child_node = NULL;
            payload->type = PAYLOAD;
            payload->count += child_count;

        }
    }
    else if (lcp == trie->skip_len)
    {
        bit = (key[KEY_BIT2IDX(length - lcp)] & (1 << ((length - lcp - 1) &0x1F))) ? 1:0;

        if (!trie->child[bit].child_node)
        {
            /* the key is going to be one of the child of existing node */
            /* should be the child */

            rv = _trie_skip_node_alloc(&node, key, bpm, length - lcp - 1, length - lcp - 1, payload, child_count);
            if (NALPM_E_SUCCESS(rv))
            {
                trie->child[bit].child_node = node;
                trie->count += child_count;
            }

        }
        else
        {
            rv = _trie_insert2(trie->child[bit].child_node,  key, bpm, length - lcp - 1,  payload, child, child_count);
            if (NALPM_E_SUCCESS(rv))
            {
                trie->count += child_count;
                if (*child != NULL)
                {
                    trie->child[bit].child_node = *child;
                    *child = NULL;
                }
            }
        }
    }
    else
    {
        trie_node_t *newchild = NULL;

        /* need to introduce internal nodes */
        node = mem_malloc2(MEM_IPUC_MODULE, sizeof(trie_node_t), trie_node_t);
        if (node == NULL)
        {
            return CTC_E_NO_MEMORY;
        }

        _CLONE_TRIE_NODE_(node, trie);

        _trie_skip_node_alloc(&newchild, key, bpm,
                              ((lcp)?length - lcp - 1:length - 1),
                              length - lcp - 1,
                              payload, child_count);

        bit = (key[KEY_BIT2IDX(length - lcp)] & (1 << ((length - lcp - 1) &0x1F))) ? 1: 0;
        node->child[!bit].child_node = trie;
        node->child[bit].child_node = newchild;
        node->type = INTERNAL;
        node->skip_addr = SHR(trie->skip_addr, trie->skip_len - lcp, 31);
        node->skip_len = lcp;
        node->count += child_count;

        *child = node;
        trie->skip_addr &= MASK(trie->skip_len - lcp - 1);
        trie->skip_len  -= (lcp + 1);

    }

    return rv;
}


/*
 * Function:
 *     _trie_merge
 * Purpose:
 *     merge or fuse the child trie with parent trie
 */
STATIC int32
_trie_merge(trie_node_t *parent_trie,
            trie_node_t *child_trie,
            uint32 *pivot,
            uint32 length,
            trie_node_t **new_parent)
{
    int32 rv, child_count;
    trie_node_t *child = NULL, clone;
    uint32 child_pivot[2] = {0};
    uint32 child_length = 0;

    _trie_search(child_trie, pivot, length, &child, child_pivot, &child_length, 0, 1);

    if (child == NULL)
    {
        return CTC_E_INVALID_PARAM;
    }

    _CLONE_TRIE_NODE_(&clone, child);

    if (child != child_trie)
    {
        rv = _trie_skip_node_free(child_trie, child_pivot, child_length);
        if (rv < 0)
        {
            return CTC_E_INVALID_PARAM;
        }
    }



    /* Record the child count before being cleared */
    child_count = child->count;

    sal_memset(child, 0, sizeof(*child));

    /* merge happens on bucket trie, which usually does not need bpm */
    rv = _trie_insert2(parent_trie, child_pivot, NULL, child_length, child,
                       new_parent, child_count);
    if (rv < 0)
    {
        return CTC_E_INVALID_PARAM;
    }

    if (child->child[0].child_node || child->child[1].child_node)
    {
        return CTC_E_INVALID_PARAM;
    }

    if (clone.type == INTERNAL)
    {
        child->type = INTERNAL;
    }

    child->child[0].child_node = clone.child[0].child_node;
    child->child[1].child_node = clone.child[1].child_node;

    return CTC_E_NONE;
}



int32
trie_merge(trie_t *parent_trie,
           trie_node_t *child_trie,
           uint32 *child_pivot,
           uint32 length)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *child = NULL;

    if (!child_trie)
    {
        return CTC_E_NONE;
    }

    if (parent_trie->trie == NULL)
    {
        parent_trie->trie = child_trie;
    }
    else
    {
        if (parent_trie->v6_key)
        {
            rv = _trie_v6_merge(parent_trie->trie, child_trie, child_pivot, length, &child);
        }
        else
        {
            rv = _trie_merge(parent_trie->trie, child_trie, child_pivot, length, &child);
        }
        if (child)
        {
            parent_trie->trie = child;
        }
    }

    return rv;
}
#if 0
STATIC int32
_trie_fuse_child(trie_node_t *trie, int32 bit)
{
    trie_node_t *child = NULL;
    int32 rv = CTC_E_NONE;

    if (trie->child[0].child_node && trie->child[1].child_node)
    {
        return CTC_E_INVALID_PARAM;
    }

    bit = (bit > 0)?1:0;
    child = trie->child[bit].child_node;

    if (child == NULL)
    {
        return CTC_E_INVALID_PARAM;
    }
    else
    {
        if (trie->skip_len + child->skip_len + 1 <= 31)
        {
            if (trie->skip_len == 0)
            {
                trie->skip_addr = 0;
            }

            if (child->skip_len < 31)
            {
                trie->skip_addr = SHL(trie->skip_addr, child->skip_len + 1, 31);
            }

            trie->skip_addr  |= SHL(bit, child->skip_len, 31);
            child->skip_addr |= trie->skip_addr;
            child->skip_len  += trie->skip_len + 1;

            /* do not free payload nodes as they are user managed */
            if (trie->type == INTERNAL)
            {
                mem_free(trie);
            }
        }
    }

    return rv;
}
#endif
#if 0
int32
_trie_split2(trie_node_t *trie,
             uint32 *key,
             uint32 key_len,
             uint32 *pivot,
             uint32 *pivot_len,
             uint32 *split_count,
             trie_node_t **split_node,
             trie_node_t **child,
             trie_split2_states_e_t *state,
             const int32 max_split_count,
             const int32 exact_same)
{
    uint32 lcp = 0;
    int32 bit = 0, rv = CTC_E_NONE;


    KEY_APPEND(pivot, pivot_len, trie->skip_addr, trie->skip_len);
    LCP_LEN(lcp, key, key_len, trie->skip_addr, trie->skip_len);

    if (lcp == trie->skip_len)
    {
        if (trie->count <= max_split_count && (!exact_same || (key_len - lcp) == 0))
        {
            *split_node = trie;
            *split_count = trie->count;

            if (trie->count < max_split_count)
            {
                *state = TRIE_SPLIT2_STATE_PRUNE_NODES;
            }

            return CTC_E_NONE;
        }

        if (key_len > lcp)
        {
            bit = (key[KEY_BIT2IDX(key_len - lcp)] & (1 << ((key_len - lcp - 1) &0x1F))) ? 1:0;

            /* based on next bit branch left or right */
            if (trie->child[bit].child_node)
            {

                KEY_APPEND(pivot, pivot_len, bit, 1);


                rv = _trie_split2(trie->child[bit].child_node,
                                  key, key_len - lcp - 1,
                                  pivot, pivot_len, split_count,
                                  split_node, child, state,
                                  max_split_count, exact_same);
                if (NALPM_E_FAILURE(rv))
                {
                    return rv;
                }

            }
        }
    }

    /* free up internal nodes if applicable */
    switch(*state)
    {
    case TRIE_SPLIT2_STATE_NONE: /* fail to split */
        break;

    case TRIE_SPLIT2_STATE_PRUNE_NODES:
        if (trie->count == *split_count)
        {
            mem_free(trie);
        }
        else
        {

            trie->child[bit].child_node = NULL;
            bit = (bit == 0)?1:0;
            trie->count -= *split_count;

            if ((trie->type == INTERNAL) &&
                (trie->skip_len + trie->child[bit].child_node->skip_len + 1 <= 31))
            {
                *child = trie->child[bit].child_node;
                rv = _trie_fuse_child(trie, bit);
                if (rv != CTC_E_NONE)
                {
                    *child = NULL;
                }
            }
            *state = TRIE_SPLIT2_STATE_DONE;
        }
        break;

    case TRIE_SPLIT2_STATE_DONE:
        if (*child != NULL)
        {
            trie->child[bit].child_node = *child;
            *child = NULL;
        }
        trie->count -= *split_count;
        break;

    default:
        break;
    }

    return rv;
}


int32
trie_split2(trie_t *trie,
                  uint32 *key,
                  uint32 key_len,
                  uint32 *pivot,
                  uint32 *pivot_len,
                  trie_node_t **split_trie_root,
                  const int32 max_split_count,
                  const int32 exact_same)
{
    int32 rv = CTC_E_NONE;
    int32 msc = max_split_count;
    uint32 split_count = 0;
    trie_node_t *child = NULL, *node = NULL, clone;
    trie_split2_states_e_t state = TRIE_SPLIT2_STATE_NONE;


    *split_trie_root = NULL;
    *pivot_len = 0;

    if (trie->trie)
    {
        if (max_split_count == 0xfffffff)
        {
            trie_node_t *child2 = NULL;
            trie_node_t *payload;
            payload = mem_malloc(MEM_IPUC_MODULE, sizeof(trie_node_t));
            if (payload == NULL)
            {
                return CTC_E_NO_MEMORY;
            }

            if (trie->v6_key)
            {
                rv = _trie_v6_insert(trie->trie, key, NULL, key_len, payload, &child2, 0);
            }
            else
            {
                rv = _trie_insert2(trie->trie, key, NULL, key_len, payload, &child2, 0);
            }
            if (child2)
            {
                trie->trie = child2;
            }

            if (NALPM_E_SUCCESS(rv))
            {
                payload->type = INTERNAL;
            }
            else
            {
                mem_free(payload);
                if (rv != CTC_E_EXIST)
                {
                    return rv;
                }
            }

            msc = trie->trie->count;
        }

        if (trie->v6_key)
        {
            sal_memset(pivot, 0, 16);
            rv = _trie_v6_split2(trie->trie, key, key_len, pivot, pivot_len,
                                 &split_count, split_trie_root, &child, &state,
                                 msc, exact_same);
        }
        else
        {
            sal_memset(pivot, 0, 8);
            rv = _trie_split2(trie->trie, key, key_len, pivot, pivot_len,
                              &split_count, split_trie_root, &child, &state,
                              msc, exact_same);
        }

        if (NALPM_E_SUCCESS(rv) && (TRIE_SPLIT2_STATE_DONE == state))
        {

            /* update the child pointer if child was pruned */
            if (child != NULL)
            {
                trie->trie = child;
            }

            sal_memcpy(&clone, *split_trie_root, sizeof(trie_node_t));
            child = *split_trie_root;

            /* take advantage of thie function by passing in internal or payload node whatever
            * is the new root. If internal the function assumed it as payload node & changes type.
            * But this method is efficient to reuse the last internal or payload node possible to
            * implant the new pivot */
            if (trie->v6_key)
            {
                rv = _trie_v6_skip_node_alloc(&node, pivot, NULL,
                                              *pivot_len, *pivot_len,
                                              child, child->count);
            }
            else
            {
                rv = _trie_skip_node_alloc(&node, pivot, NULL,
                                           *pivot_len, *pivot_len,
                                           child, child->count);
            }

            if (NALPM_E_SUCCESS(rv))
            {
                if (clone.type == INTERNAL)
                {
                    child->type = INTERNAL; /* since skip alloc would have reset it to payload */
                }
                child->child[0].child_node = clone.child[0].child_node;
                child->child[1].child_node = clone.child[1].child_node;
                *split_trie_root = node;
            }
        }
        else if (NALPM_E_SUCCESS(rv) && (max_split_count == 0xfffffff) &&
            (split_count == trie->trie->count))
        {

            *split_trie_root = trie->trie;
            trie->trie = NULL;
        }
        else
        {
            rv = CTC_E_NOT_EXIST;
        }
    }
    else
    {
        rv = CTC_E_INVALID_PARAM;
    }

    return rv;
}
#endif

#define TRIE_TRAVERSE_STOP(state, rv)  {if (state == TRIE_TRAVERSE_STATE_DONE || rv < 0) {return rv;} }

STATIC int32 _trie_preorder_traverse2(trie_node_t *ptrie,
                                      trie_node_t *trie,
                                      trie_traverse_states_e_t *state,
                                      trie_callback_ext_f cb,
                                      void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *lc, *rc;

    if (trie == NULL || !cb)
    {
        return CTC_E_NONE;
    }
    else
    {
        /* make the trie delete safe */
        lc = trie->child[0].child_node;
        rc = trie->child[1].child_node;

        if (trie->type == PAYLOAD)
        {
            rv = cb(ptrie, trie, state, user_data);
            TRIE_TRAVERSE_STOP(*state, rv);

            if (*state != TRIE_TRAVERSE_STATE_DELETED)
            {
                ptrie = trie;
            }
        }
    }

    if (NALPM_E_SUCCESS(rv))
    {
        rv = _trie_preorder_traverse2(ptrie, lc, state, cb, user_data);
        TRIE_TRAVERSE_STOP(*state, rv);
    }

    if (NALPM_E_SUCCESS(rv))
    {
        rv = _trie_preorder_traverse2(ptrie, rc, state, cb, user_data);
    }
    return rv;
}

STATIC int32
_trie_postorder_traverse2(trie_node_t *ptrie,
                                       trie_node_t *trie,
                                       trie_traverse_states_e_t *state,
                                       trie_callback_ext_f cb,
                                       void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *ori_ptrie = ptrie;
    trie_node_t *lc, *rc;
    node_type_e_t trie_type;

    if (trie == NULL)
    {
        return CTC_E_NONE;
    }

    /* Change the ptrie as trie if applicable */
    if (trie->type == PAYLOAD)
    {
        ptrie = trie;
    }

    trie_type = trie->type;
    lc = trie->child[0].child_node;
    rc = trie->child[1].child_node;

    if (NALPM_E_SUCCESS(rv))
    {
        rv = _trie_postorder_traverse2(ptrie, lc, state, cb, user_data);
        TRIE_TRAVERSE_STOP(*state, rv);
    }
    if (NALPM_E_SUCCESS(rv))
    {
        rv = _trie_postorder_traverse2(ptrie, rc, state, cb, user_data);
        TRIE_TRAVERSE_STOP(*state, rv);
    }
    if (NALPM_E_SUCCESS(rv))
    {
        if (trie_type == PAYLOAD)
        {
            rv = cb(ori_ptrie, trie, state, user_data);
        }
    }
    return rv;
}


int32
 sys_nalpm_trie_traverse_lr(trie_node_t *trie,
                                    trie_traverse_states_e_t *state,
                                    trie_callback_ext_f cb,
                                    void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *lc, *rc;

    if (trie == NULL) {
        return CTC_E_NONE;
    }

    lc = trie->child[0].child_node;
    rc = trie->child[1].child_node;

    if (NALPM_E_SUCCESS(rv) && lc && lc->count >= 4)
    {
        rv = sys_nalpm_trie_traverse_lr(lc, state, cb, user_data);
        if(NALPM_E_FAILURE(rv))
        {
            return rv;
        }
    }

    if (NALPM_E_SUCCESS(rv) && rc && rc->count >= 4)
    {
        rv = sys_nalpm_trie_traverse_lr(rc, state, cb, user_data);
        if (NALPM_E_FAILURE(rv))
        {
            return rv;
        }
    }

    if (NALPM_E_SUCCESS(rv)) {
        rv = cb(NULL, trie, state, user_data);
    }

    return rv;
}


STATIC int32
_trie_inorder_traverse2(trie_node_t *ptrie,
                                     trie_node_t *trie,
                                     trie_traverse_states_e_t *state,
                                     trie_callback_ext_f cb,
                                     void *user_data)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *rc = NULL;
    trie_node_t *ori_ptrie = ptrie;

    if (trie == NULL)
    {
        return CTC_E_NONE;
    }

    /* Change the ptrie as trie if applicable */
    if (trie->type == PAYLOAD)
    {
        ptrie = trie;
    }

    rv = _trie_inorder_traverse2(ptrie, trie->child[0].child_node, state, cb, user_data);
    TRIE_TRAVERSE_STOP(*state, rv);

    /* make the trie delete safe */
    rc = trie->child[1].child_node;

    if (NALPM_E_SUCCESS(rv))
    {
        if (trie->type == PAYLOAD)
        {
            rv = cb(ptrie, trie, state, user_data);
            TRIE_TRAVERSE_STOP(*state, rv);
            if (*state == TRIE_TRAVERSE_STATE_DELETED)
            {
                ptrie = ori_ptrie;
            }
        }
    }

    if (NALPM_E_SUCCESS(rv))
    {
        rv = _trie_inorder_traverse2(ptrie, rc, state, cb, user_data);
    }
    return rv;
}



STATIC int32
_trie_traverse2(trie_node_t *trie, trie_callback_ext_f cb,
                void *user_data,  trie_traverse_order_e_t order,
                trie_traverse_states_e_t *state)
{
    int32 rv = CTC_E_NONE;

    switch(order)
    {
    case _TRIE_PREORDER_TRAVERSE:
        rv = _trie_preorder_traverse2(NULL, trie, state, cb, user_data);
        break;
    case _TRIE_POSTORDER_TRAVERSE:
        rv = _trie_postorder_traverse2(NULL, trie, state, cb, user_data);
        break;
    case _TRIE_INORDER_TRAVERSE:
        rv = _trie_inorder_traverse2(NULL, trie, state, cb, user_data);
        break;
    default:
        break;
    }

    return rv;
}



int32
sys_nalpm_trie_traverse2(trie_t *trie, trie_callback_ext_f cb,
                               void *user_data, trie_traverse_order_e_t order)
{
    trie_traverse_states_e_t state = TRIE_TRAVERSE_STATE_NONE;


    if (trie == NULL)
    {
        return CTC_E_NONE;
    }
    else
    {
        return _trie_traverse2(trie->trie, cb, user_data, order, &state);
    }
}



int32
trie_delete (trie_t * trie,
             uint32 *key, uint32 length, trie_node_t ** payload)
{
    int32 rv = CTC_E_NONE;
    trie_node_t *child = NULL;

    if (trie->trie)
    {
        if (trie->v6_key)
        {
            rv = sys_trie_v6_delete (trie->trie, key, length, payload, &child);
        }
        else
        {
            rv = _trie_delete (trie->trie, key, length, payload, &child);
        }

        if (rv == CTC_E_IN_USE)
        {
            /* the head node of trie was deleted, reset trie pointer to null */
            trie->trie = NULL;
            rv = CTC_E_NONE;
        }
        else if (rv == CTC_E_NONE && child != NULL)
        {
            trie->trie = child;
        }
    }
    else
    {
        rv = CTC_E_ENTRY_NOT_EXIST;
    }
    return rv;
}



int32
trie_destroy (trie_t * trie)
{

    mem_free (trie);
    return CTC_E_NONE;
}


int32
sys_trie_v4_find_lpm_prefix (trie_node_t * trie,
                   uint32 *pivot,
                   uint32 *length)
{
    if (!trie)
        return CTC_E_INVALID_PARAM;


    if (trie->child[0].child_node && trie->child[1].child_node)
    {
        return 0;
    }

    if (trie->child[0].child_node)
    {
       KEY_APPEND(pivot, length, trie->skip_addr, trie->skip_len);
        sys_trie_v4_find_lpm_prefix(trie->child[0].child_node, pivot, length);

    }
    else if(trie->child[1].child_node)
    {
       KEY_APPEND (pivot, length, trie->skip_addr, trie->skip_len);
        sys_trie_v4_find_lpm_prefix(trie->child[1].child_node, pivot, length);
    }
    else
    {
        return 0;
    }

    return 0;
}

int32
sys_trie_find_lpm_prefix(trie_t * trie,
                   uint32 *pivot,
                   uint32 *length)
{
    int32 rv = 0;

    if (!trie || !pivot || !length)
    {
        return CTC_E_INVALID_PARAM;
    }

    if (trie->v6_key)
    {
        sal_memset (pivot, 0, 16);

        rv = sys_trie_v6_find_lpm_prefix (trie->trie, pivot, length);
    }
    else
    {
        sal_memset (pivot, 0, 8);

        rv = sys_trie_v4_find_lpm_prefix (trie->trie, pivot, length);
    }

    return rv;
}


STATIC int32
_trie_find_lpm_sub_route(trie_node_t *trie,
                         uint32 *pivot,
                         uint32 *length,
                         trie_check_cb_f cb,
                         trie_chk_info_t *info)
{
    uint8 bit = 0;
    uint8 chd = 0;
    trie_node_t * sub_trie = NULL;
    uint32 ip = 0;
    trie_dump_node_t *p_dump_node = info->dump_node;

    if (trie == NULL)
    {
        return 0;
    }

    if (trie->child[0].child_node == NULL
        && trie->child[1].child_node == NULL)
    {
        ip = (*pivot << (32 - *length));
        cb(info->lchip, info, &ip);
    }
    else
    {
        for (chd = 0; chd < 2; chd++)
        {
            sub_trie = trie->child[chd].child_node;
            KEY_APPEND(pivot, length, chd, 1);

            if (sub_trie == NULL)
            {
                ip = (*pivot << (32 - *length));
                cb(info->lchip, info, &ip);
            }
            else
            {
                trie_dump_node_t dump_node;
                sal_memcpy(&dump_node, p_dump_node, sizeof(trie_dump_node_t));
                dump_node.father = sub_trie;
                dump_node.father_lvl = p_dump_node->father_lvl + 1;
                info->dump_node = &dump_node;
                if (info->debug_en)
                {
                    info->cb(sub_trie, &dump_node);
                }

                if (sub_trie->type == PAYLOAD)
                {
                    if (sub_trie->skip_len > 0)
                    {
                        bit = (sub_trie->skip_addr >> (sub_trie->skip_len - 1));
                        KEY_APPEND(pivot, length, bit == 0?1:0, 1);
                        ip = (*pivot << (32 - *length));
                        cb(info->lchip, info, &ip);
                        _key_shift_right(pivot, 1);
                        *length = *length - 1;
                    }
                }
                else
                {
                    KEY_APPEND(pivot, length, sub_trie->skip_addr, sub_trie->skip_len);
                    _trie_find_lpm_sub_route(sub_trie, pivot, length, cb, info);
                    _key_shift_right(pivot, sub_trie->skip_len);
                    *length = *length - sub_trie->skip_len;
                }
            }

            _key_shift_right(pivot, 1);
            *length = *length - 1;
        }
    }

    return 0;
}


STATIC int32
_trie_find_lpm_route (trie_node_t * trie,
                      uint32 *key,
                      uint32  key_len,
                      uint32 *pivot,
                      uint32 *length,
                      trie_check_cb_f cb,
                      trie_chk_info_t *info)
{
    uint32 lcp = 0;
    int32 bit = 0, rv = CTC_E_NONE;
    trie_dump_node_t *p_dump_node = info->dump_node;
    trie_dump_node_t dump_node;
    if (trie == NULL)
    {
        return 0;
    }
    sal_memcpy(&dump_node, p_dump_node, sizeof(trie_dump_node_t));
    if (info->debug_en)
    {
        info->cb (trie, &dump_node);
    }

     LCP_LEN(lcp, key, key_len, trie->skip_addr, trie->skip_len);

    if ((key_len > trie->skip_len) && (lcp == trie->skip_len))
    {
        bit = (key[KEY_BIT2IDX(key_len - lcp)] & SHL(1, (key_len - lcp - 1)&0x1F, 32)) ? 1 : 0;

        KEY_APPEND(pivot, length, trie->skip_addr, trie->skip_len);

        /* based on next bit branch left or right */
        if (trie->child[bit].child_node)
        {
            KEY_APPEND(pivot, length, bit, 1);

            dump_node.father = trie;
            dump_node.father_lvl = p_dump_node->father_lvl + 1;
            info->dump_node = &dump_node;
            return _trie_find_lpm_route (trie->child[bit].child_node, key, key_len - lcp - 1, pivot, length, cb, info);
        }
    }
    else if ((key_len == trie->skip_len) && (lcp == key_len))
    {
        if (trie->type == PAYLOAD)
        {
            /* exact match case */
            KEY_APPEND(pivot, length, trie->skip_addr, trie->skip_len);
            _trie_find_lpm_sub_route(trie, pivot, length, cb, info);
        }
    }
    return rv;
}

/*
* Function:
*     sys_nalpm_trie_find_lpm
* Purpose:
*     Find the longest prefix matched with given prefix
*/
int32
sys_trie_check_node (trie_t * trie,
                     uint32 *key,
                     uint32  key_len,
                     trie_check_cb_f cb,
                     trie_chk_info_t *info)
{
    uint32 pivot[4] = {0};
    uint32 length = 0;
    trie_dump_node_t dump_node;

    sal_memset(&dump_node, 0, sizeof(trie_dump_node_t));
    dump_node.father = trie->trie;
    dump_node.father_lvl = 0;
    dump_node.root =  trie->trie;
    dump_node.user_data = NULL;
    info->dump_node = &dump_node;
    info->debug_en = 0;

    SYS_NALPM_CONVERT_TO_LSB(key, key_len, trie->v6_key);

    if (trie->trie)
    {
        if (trie->v6_key)
        {
            return _trie_v6_find_lpm_route (trie->trie, key, key_len, pivot, &length, cb, info);
        }
        else
        {
            return _trie_find_lpm_route (trie->trie, key, key_len, pivot, &length, cb, info);
        }
    }

    return CTC_E_NOT_EXIST;
}
#endif

